package letcode.oneQuestionPerDay._202004._09;

import java.util.*;

/**
 * @Description: 括号生成
 * @Date: 2020/4/9
 * @Author: 许群星
 */
public class BracketGenerating {
    public static void main(String[] args) {
        int a=3;
        List<String> list=generateParenthesis(a);
        for (String s:list
             ) {
            System.out.println(s);
        }
    }
    //提供方法   超出时间限制
    public static List<String> generateParenthesis(int n) {
        List<String> ans=new ArrayList<>();
        //得到所有的排列，去除掉无效的。
        String str="";
        for (int i = 0; i < n; i++) {
            str+="()";
        }
//        System.out.println(str);
        List<String> all=getAll(str);
        for (String s:all
             ) {
            if (isEffective(s)&&!ans.contains(s)) {
                ans.add(s);
            }
        }

        return ans;
    }
    //得到所有排列
    public static List<String> getAll(String str){
        List<String> list=new ArrayList<>();
        char[] chars=str.toCharArray();
        rank(chars,0,chars.length,list);
        return list;

    }
    public static void rank(char[] t,int k,int n,List<String> list){
        if (k==n-1){
            String haha="";
            for (int i = 0; i < n; i++) {
                haha+=t[i];
//                System.out.print(t[i]);
            }
            list.add(haha);
//            System.out.println();
        }else {
            for (int i = k; i < n; i++) {
                //先交换，调用函数之后，在换回来
                char temp=t[i];t[i]=t[k];t[k]=temp;
                rank(t,k+1,n,list);
                temp=t[i];t[i]=t[k];t[k]=temp;
            }
        }
    }
    //筛选有效的
    public static boolean isEffective(String str){
        if (null==str||"".equals(str))
            return true;
        Stack<Character> stack=new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i)=='('){
                stack.push(str.charAt(i));
            }else {
                if (stack.isEmpty())
                    return false;
                if (!(stack.pop()=='('&&str.charAt(i)==')'))
                    return false;
            }
        }
        return stack.isEmpty();
    }
}
/*
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */